#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int ans = 0, f = 0;
    char c = getchar();
    while (!isdigit(c))
        f |= c == '-', c = getchar();
    while (isdigit(c))
        ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
    return f ? -ans : ans;
}
void write(long long x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(48 + x % 10);
}
const int N = 3e3 + 5;
int n, m, f[N], mp[N * N];
struct edge
{
    int u, v, w;
    inline bool operator<(const edge &x) const { return w < x.w; }
} a[N * N];
int find(int v) { return f[v] == v ? v : f[v] = find(f[v]); }
signed main()
{
    freopen("up.in", "r", stdin);
    freopen("up.out", "w", stdout);
    int T = read();
    while (T--)
    {
        n = read(), m = read();
        if (m == 0)
        {
            write(n - 1), putchar('\n');
            continue;
        }
        int cnt = 0;
        for (int i = 1; i <= n; f[i] = i, ++i)
            for (int j = i + 1; j <= n; ++j)
                a[++cnt] = {i, j, abs(i - j)}, mp[(i - 1) * n + j] = cnt;
        while (m--)
        {
            int u = read(), v = read(), w = read();
            if (u > v)
                swap(u, v);
            a[mp[(u - 1) * n + v]].w = w;
        }
        long long ans = 0;
        sort(a + 1, a + cnt + 1);
        for (int i = 1; i <= cnt; ++i)
        {
            int u = a[i].u, v = a[i].v, w = a[i].w;
            if ((u = find(u)) != (v = find(v)))
                ans += w, f[u] = v;
        }
        write(ans), putchar('\n');
    }
    return 0;
}
